`
https://leetcode.cn/problems/nth-magical-number/
`

/**
 * @param {number} n
 * @param {number} a
 * @param {number} b
 * @return {number}
 */
var nthMagicalNumber = function (n, a, b) {
  // 计算第 n 个神奇数字 x ，也就是计算 <= x 的神奇数字有 n 个
  const _lcm = lcm(a, b)

  // 计算 <= x 的神奇数字个数是否 >= n
  // a 的倍数个数 + b 的倍数个数 - a 和 b 的公倍数个数
  const check = (x) => Math.floor(x / a) + Math.floor(x / b) - Math.floor(x / _lcm) >= n

  // 神奇数字最小是 min(a, b)，第 n 个神奇数字至少是 min(a, b) + n − 1，再减一就一定无法满足要求
  let left = Math.min(a, b) + n - 2
  let right = Math.min(a, b) * n
  while (left + 1 < right) {
    const mid = left + Math.floor((right - left) / 2)
    if (check(mid)) {
      right = mid
    } else {
      left = mid
    }
  }
  return right % (1e9 + 7)
};

function gcd(a, b) {
  a = Math.abs(a);
  b = Math.abs(b);
  while (b !== 0) {
    [a, b] = [b, a % b];
  }
  return a;
}

function lcm(a, b) {
  return Math.abs(a * b) / gcd(a, b);
}